#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <cstdlib>
#include <ctime>

#define N 20

using namespace std; 

int n; 
int g_start_col[N]; 
int g_col[N], g_l45[2*N], g_l135[2*N]; 

inline int l45_idx(int row, int col)
{
	return row + col; 
}

int l135_idx(int row, int col)
{
	return n - 1 - (col - row); 
}

bool dfs(int row)
{
	bool ret; 
	int i45, i135; 
	
	if (row==n) {
		return true; 
	}
	
	for (int col=g_start_col[row]; col<n; col++) {
		if (g_col[col])
			continue; 
		i45 = l45_idx(row, col); 
		if (g_l45[i45])
			continue; 
		i135 = l135_idx(row, col); 
		if (g_l135[i135])
			continue; 
		g_col[col] = g_l45[i45] = g_l135[i135] = 1; 
		ret = dfs(row+1); 
		if (ret==true) {
			g_start_col[row] = col; 
			return true; 
		} 
		g_col[col] = g_l45[i45] = g_l135[i135] = 0; 
	}
	g_start_col[row] = 0; 
	return false; 
}

int main()
{
	int c=0; 
	cin>>n; 
	
	while(dfs(0)==true) {
		int i; 
		memset(g_col, 0, sizeof(g_col)); 
		memset(g_l45, 0, sizeof(g_l45)); 
		memset(g_l135, 0, sizeof(g_l135)); 
		c++; 
		if (c<=3) {
			for (i=0; i<n; i++) {
				if (i) {
					cout<<" "; 
				}
				cout<<g_start_col[i]+1; 
			}
			cout<<endl; 
		}
				
		for (i=n-1; i>=0; i--) {
			if (g_start_col[i]<n) {
				g_start_col[i]++; 
				break; 
			} else {
				g_start_col[i] = 0; 
			}
		}
		if (i<0) {
			break; 
		}
	}
	cout<<c<<endl; 
	return 0; 
}


